/*
https://leetcode.cn/problems/count-subtrees-with-max-distance-between-cities/description/

*/

---------------------------------------------------------------------------------


#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    /**
     * 清除掩码中的第n位。
     *
     * @param Mask 引用传递的掩码变量
     * @param N 要清除的位的位置
     * @return 返回更新后的掩码值
     */
    int BitClr(int &Mask, int N) {
        Mask = Mask & (~(1 << N));
        return Mask;
    }

    /**
     * 深度优先搜索，计算以当前节点为根的最大路径长度，并更新最大直径。
     *
     * @param Root 当前节点索引
     * @param Mask 引用传递的掩码变量，表示当前考虑的节点集合
     * @param MaxD 引用传递的最大直径变量
     * @param Graph 邻接表表示的图结构
     * @return 返回从当前节点出发的最大路径长度
     */
    int Dfs(int Root, int &Mask, int &MaxD, vector<vector<int>> &Graph) {
        int First = 0; // 第一大路径长度
        int Second = 0; // 第二大路径长度
        BitClr(Mask, Root); // 清除当前节点在掩码中的标志

        // 遍历与当前节点相邻的所有节点
        for (auto V : Graph[Root]) {
            if ((1 << V) & Mask) { // 如果相邻节点还在掩码中（即未访问过）
                BitClr(Mask, V); // 清除相邻节点的标志
                int Curr = 1 + Dfs(V, Mask, MaxD, Graph); // 计算相邻节点的最大路径长度

                // 更新第一大和第二大路径长度
                if (Curr > First) {
                    Second = First;
                    First = Curr;
                } else if (Curr > Second) {
                    Second = Curr;
                }
            }
        }

        // 更新最大直径
        MaxD = max(MaxD, First + Second);
        return First; // 返回从当前节点出发的最大路径长度
    }

    /**
     * 计算每个直径的子图数量。
     *
     * @param N 节点总数
     * @param Edges 边的列表
     * @return 每个直径对应的子图数量
     */
    vector<int> CountSubgraphsForEachDiameter(int N, vector<vector<int>>& Edges) {
        vector<vector<int>> Graph(N); // 邻接表表示的图结构
        vector<int> Ans(N - 1, 0); // 存储结果，初始化为0

        // 构建图结构
        for (auto E : Edges) {
            int X = E[0] - 1;
            int Y = E[1] - 1;
            Graph[X].push_back(Y);
            Graph[Y].push_back(X);
        }

        // 遍历所有可能的节点组合
        for (int I = 1; I < (1 << N); ++I) {
            int Mask = I; // 当前考虑的节点组合
            int MaxD = 0; // 当前组合的最大直径
            int Root = 32 - __builtin_clz(I) - 1; // 找到最高位的1作为根节点

            // 如果掩码中还有剩余节点未访问，则跳过此组合
            if (Dfs(Root, Mask, MaxD, Graph) && Mask != 0) continue;

            // 如果最大直径大于0，则更新结果数组
            if (MaxD > 0) Ans[MaxD - 1]++;
        }

        return Ans;
    }
};


-----------------------------------------------------------------------------------------